# 386 中等：字典序排数
import functools


def lexicalOrder(n: int):

    def dictSort(str1, str2):
        length = min(len(str1), len(str2))
        for j in range(length):
            if str1[j] > str2[j]:
                return 1
            elif str1[j] < str2[j]:
                return -1
        return 0

    arr = []
    for i in range(1, n + 1):
        arr.append(str(i))
    arr = sorted(arr, key=functools.cmp_to_key(dictSort))
    return [int(c) for c in arr]

            # ans = [0] * n
            # num = 1
            # for i in range(n):
            #     ans[i] = num
            #     if num * 10 <= n:
            #         num *= 10
            #     else:
            #         while num % 10 == 9 or num + 1 > n:
            #             num //= 10
            #         num += 1
            # return ans


print(lexicalOrder(120))
